1. Field of the Invention
The invention relates to a parallel cyclic code generation device for generating a cyclic code for use in detecting a bit error inside transfer frames in data communications, and also relates to a parallel cyclic code error detection device for inspecting a cyclic code for use in detecting a bit error inside transfer frames in data communications.
2. Description of Related Art
In recent years, there have been advances in broader bandwidths for a frame rate in data communications technology including 40 Gigabit Ethernet, and 100 Gigabit Ethernet, as specified by U.S. IEEE 802 committee. Herein, Ethernet is a registered trademark. In processing for the frame rate in broader bandwidths, there are limitations to a processing rate by use of a serial signal, so that parallel expansion processing for frame signals (hereinafter referred to as parallelization) is essential.
In data communications, error control techniques, such as frame error detection and frame error correction is important for reliable frame transmission. A cyclic code is popular for detection of an error in a frames and correction of the error. The cyclic code includes a CRC (Cyclic Redundancy Check) code, hamming code, BCH code, and so forth, and those cyclic codes are in widespread use in a data communications technology as well.
In order to realize the higher speed data communications, it is necessary to establish broader bandwidth error control technologies by a cyclic code, especially CRC code. For that purpose, there is the need for CRC code computation processing of a parallelization signal of M bits, where M represents an optional positive integer not less than 2.
If an input frame length (n bits, where n represents a positive integer not less than 1) is not an integral multiple of a parallel width (M bits), fraction bits (which means the valid bits is less than M) are generated at the final processing word of the frame data. If parallel data containing the fraction bits is processed in a CRC calculation circuit of M bits, even invalid bits data other than the fraction bits will fall in a computation range of CRC codes, so that it is not possible to obtain a correct computation results.
A method for the parallel CRC computation for an input frame containing this kind of fraction bits is revealed in a letter contributed by H. Michael Ji, and Earl Killian to IEEE ICC 2002 (International Conference on Communications 2002), under the title of “Fast Parallel CRC Algorithm and Implementation on a Configurable Processor” (Non-patent Document 1).
There will be described hereinafter an example of a configuration of a CRC computation method relating to the invention. FIG. 18 is a block diagram showing an example of the configuration of a CRC computation method disclosed in Non-patent Document 1. Herein, there is shown the CRC calculation circuit for an input frame of M bits in width by way of example. The CRC calculation circuit, illustrated in FIG. 18, comprises a buffering unit 160-1, a read-out controller 160-2, a frame data rearrangement unit 160-3, a CRC computation unit 1604, and a frame length counter 160-5.
The buffering unit 160-1 is supplied with, as input signals, a frame signal parallel-expanded to M bits in width, SOF (Start of Frame) information indicative of the head of the frame, and final word valid data information H(k) indicative of the end of the frame. The buffering unit 160-1 buffers the input frame and supplies the frame length counter 160-5 with a count enable signal CEN indicating that the frame is being buffered.
The frame length counter 160-5 counts a length of the frame on the basis of the count enable signal CEN from the buffering unit 160-1. Then, the frame length counter 160-5 supplies the frame length (referred to as frame length information LEN) to the read-out controller 160-2 and the frame data rearrange unit 160-3.
The read-out controller 160-2 executes read-out of frame data blocks from the buffering unit 160-1 on the basis of the frame length information LEN from the frame length counter 160-5, thereby delivering the frame data blocks to the frame data rearrangement unit 160-3.
The frame data rearrange unit 160-3 rearranges the frame data blocks such that invalid data blocks will be at the header of the frame according to the frame length information LEN from the frame length counter 160-5. A region of the invalid data blocks has a value ‘0’.
The CRC computation unit 160-4 executes CRC computation of the frame data of M bits in width, produced by the frame data rearrangement unit 160-3.
Referring now to FIGS. 19A and 19B, there will be described an operation of the CRC calculation circuit illustrated in FIG. 18. FIGS. 19A and 19B are a schematic illustration showing an example of rearrangement of the frame data in the CRC calculation circuit illustrated in FIG. 18. FIG. 19A shows an example of input frame data in the case of a parallel width M=8 bits, and a frame length n=29 bits. The final word valid data information H(k) represents bit numbers of fraction bits, being ‘5’ in this example. In FIGS. 19A and 19B, a data unit as an object of CRC computation is indicated by ‘18-1-1’ to ‘18-4-5’, while a black filled-in portion of the input frame data indicates data units (invalid data units) other than the subjects of the CRC computation.
Upon the frame data, illustrated in FIG. 19A, being inputted, the buffering unit 160-1 buffers the frame data and delivers the count-enable signal CEN to the frame length counter 160-5.
The frame length counter 160-5 counts the frame length on the basis of the count-enable signal CEN. Upon the final word valid data information H(k) being received, the buffering unit 160-1 completes buffering, and the frame length counter 160-5 delivers the frame length information LEN to the read-out controller 160-2 and the frame data rearrangement unit 160-3. The read-out controller 160-2 reads out the frame data from the buffering unit 160-1 on the basis of the frame length information LEN from the frame length counter 160-5, thereby delivering the frame data to the frame data rearrangement unit 160-3.
The frame data rearrangement unit 160-3 counts the number of the invalid data blocks (3 bits in this case) from the frame length information LEN (29 bits in this example) and the parallel width M=8 bits, thereby rearranging the frame data so that the invalid data becomes the header of the frame. FIG. 19B shows data units rearranged by the frame data rearrangement unit 160-3 to be produced. A portion at the leading head of the frame data, corresponding to 3 bits (a black portion in FIG. 19B), represents the invalid data, and the region of the invalid data has a value ‘0’. The rearranged data units including the invalid data units positioned at the head have 32 bits in total, which is a multiple of the parallel width M=8 bits. Inasmuch as the value of the region of the invalid data units is ‘0’, results of the CRC computation are not affected. The CRC computation unit 160-4 of 8 bits in width executes CRC computation against an output of the frame data rearrangement unit 160-3, thereby obtaining correct results of the CRC computation of ‘18-1-1’ to ‘18-4-5’, illustrated in FIG. 19B, each as the data unit of a frame as the object of the CRC computation.
In Japanese Unexamined Patent Application Publication No. 2002-359561 (Patent Document 1), there is described the CRC calculation circuit for serial data of CRC-32.
With the CRC computation method disclosed in Non-patent Document 1, however, it is necessary to calculate a frame length beforehand in order to rearrange the frame data blocks. In the case of a frame where the frame length information LEN (length information) is contained in the header of a frame, the frame length information LEN can be easily acquired, however, in the case where frame length information is not held in the header of a frame as with the case of an Ethernet frame, it is necessary to execute buffering in order to acquire the frame length. In the configuration illustrated in FIG. 18, processing at the buffering unit 160-1 and processing at the frame length counter 160-5 correspond to processing for calculating the frame length.
Buffering processing executed as above will cause the following problem.
Firstly, there will be an increase in processing delay. Inasmuch as buffering is executed in order to calculate a frame length, there is the need for buffering at least one frame or more. Accordingly, processing time for buffering, commensurate with the frame length, is required, resulting in an increase in delay
Secondly, there will be an increase in circuit size. As in the case of the configuration illustrated in FIG. 18, if the buffering unit 160-1, the read-out controller 160-2, the frame length counter 160-5, and the frame data rearrangement unit 160-3 are installed in the front stage of the CRC computation unit 160-4, this will cause a system in whole to increase in scale.
Thirdly, there will be constraints on implementation of a broader band. This problem is attributable to buffering of a broadband. An upper limit occurs to a processing band for buffering owing to band constraints of a memory in use and a circuit operating speed. In a frame communications technology of several tens of Gbps class, there are needs for not only an increase in the parallel width M of frame processing but also an increase in processing clock speed, but due to presence of constraints on an input/output band of the memory, in particular, broadening of the band is constrained. In the method for the parallel CRC computation, using buffering, illustrated in FIG. 18, the memory is used for the buffering, and constraints occur to the speed, so that constraints occur to the implementation of the broader band, as well.